package my.jwds.p474;

public class FindMaxForm {

    public static void main(String[] args) {
        FindMaxForm obj = new FindMaxForm();
        String[]strs = {"10","0001","111001","1","0"};
        int m = 5;
        int n = 3;
        System.out.println(obj.findMaxForm(strs,m,n));
    }

    public int findMaxForm(String[] strs, int m, int n) {
        int [][][] dp = new int[strs.length+1][m+1][n+1];
        for (int i = 1; i <= strs.length; i++) {
            int zeros = 0;
            int ones = 0;
            String s = strs[i-1];
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '0')zeros++;
                else if (s.charAt(j) == '1')ones++;
            }
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if (j >= zeros && k >= ones){
                        dp[i][j][k] = Integer.max(dp[i][j][k],dp[i-1][j-zeros][k-ones]+1);
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }
}